package xyz.scootaloo.oj.iq

import org.junit.Test

/**
 * @author flutterdash@qq.com
 * @since 2021/4/15 9:32
 */
class M0105 {

    /**
     * input: red
     * output: apple
     * 对齐        r  e  d <i>
     *      a  p  p  l  e <j>
     *
     *
     */
    private fun oneEditAway0(first: String, second: String): Boolean {
        fun dp(i: Int, j: Int): Int {
            if (i == -1) return j + 1
            if (j == -1) return i + 1
            if (first[i] == second[j])
                return dp(i - 1, j) + 1
            val delete = dp(i - 1, j) + 1
            val replace = dp(i - 1, j - 1) + 1
            val insert = dp(i, j - 1) + 1
            return Math.min(Math.min(delete, replace), insert)
        }
        return dp(first.length - 1, second.length - 1) <= 1
    }

    /**
     * first convert to second
     *      0  1  2 [first]
     *   0  r  e  d
     * 0 a  1  2  3
     * 1 p  2  2  3
     * 2 p  3  3  3
     * 3 l  4  4  4
     * 4 e  5  5  5
     * [second]
     */
    private fun oneEditAway1(first: String, second: String): Boolean {
        // 根据first和second创建一个dp数组
        val fSize = first.length
        val sSize = second.length
        val dp = Array(size = sSize + 1, init = { IntArray(fSize + 1) })

        // 初始化dp数组
        for (fPos in 1..fSize)
            dp[0][fPos] = fPos
        for (sPos in 1..sSize)
            dp[sPos][0] = sPos

        // 遍历
        for (fPos in 1..fSize) {
            for (sPos in 1..sSize) {
                if (first[fPos - 1] == second[sPos - 1]) {
                    // first第fPos个字符和second第sPos个字符相等, 无需处理
                    dp[sPos][fPos] = dp[sPos- 1][fPos - 1]
                } else {
                    // 求 增 删 改 的最小步骤
                    dp[sPos][fPos] = min(
                        dp[sPos - 1][fPos],
                        dp[sPos - 1][fPos - 1],
                        dp[sPos][fPos - 1]
                    ) + 1
                }
            }
        }

        // 返回是否能一步走完
        return dp[sSize][fSize] <= 1
    }

    private fun min(a: Int, b: Int, c: Int): Int {
        return Math.min(a, Math.min(b, c))
    }

    @Test
    fun test0() {
        println(oneEditAway0("red", "apple"))
    }

    @Test
    fun test1() {
        println(oneEditAway1("red", "apple"))
        println(oneEditAway1("red", "rd"))
    }

}
